# LeetCode 8、字符串转换整数 (atoi)

# 一、题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 
class Solution {
 public int myAtoi(String str) {

        // 字符串的长度
    int n = str.length();

        // 设置有效数字的索引位置，初始化在第 0 个
    int index = 0;

        // 接收最终的结果
    int res = 0;

        // 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        // 所以在扫描的过程中，需要不断的判断最终的结果是正数还是负数
        // 根据字符的正和负来判断，最后一个字符决定
        // 默认为正数，即不是负数
    boolean negative = false;
    


    // 根据第一点要求：读入字符串并丢弃无用的前导空格
  while( index < n && str.charAt(index) == ' ') {

            // 有效数字的索引位置不断移动
   index++;

  }

  // 根据第四点要求：如果字符串全是空格直接返回 0
  if( index == n) {
            
            // 直接返回 0
   return 0;

  }

  // 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        // 如果发现是负数，修改判断
  if( str.charAt(index) == '-' ) {

            // 认为是负数
   negative = true;

  }

  // 跳过正负号符号位
  if( str.charAt(index) == '-' || str.charAt(index) == '+' ) {

   // 有效数字的索引位置不断移动
   index++;

  }

  // 开始获取数字，一个数字一个数字去获取
        // 由于在字符串中可能存在数字之间夹杂的其它字符，所以出现这种情况需要截断
  while( index < n && str.charAt(index) >= '0' && str.charAt(index) <= '9' ) {

   // '0'的 ASCII 码是48，'1' 的是 49 
            // 获取数字，相当于字符串转整数操作
   int lastNum = str.charAt(index) - 48 ;

   // 根据第五点要求：需要判断数字是否合理
            // 先判断正数情况，大于 2147483647 的整数应该被固定为 2147483647 
            // 即如何发现之前积累的数字都大于了 214748364，比如最小为 214748365
            // 那么无论 lastNum 为多少，添加到尾部都会大于 214748364
   if( !negative && ( res > 214748364 || ( res == 214748364 && (lastNum == 8 || lastNum == 9 )))) {

                // 应该被固定为 2147483647 
    return 2147483647;

   }

   // 根据第五点要求：需要判断数字是否合理
            // 再判断负数情况，小于 -2147483648 的整数应该被固定为 -2147483648 
   if( negative && ( -res < -214748364 || ( -res == -214748364 && (lastNum == 8 || lastNum == 9 ) ))) {
    // 应该被固定为 -2147483648 
                return -2147483648;
   }

            // 否则说明可以添加上去
   res = res * 10 + lastNum;

            // 有效数字的索引位置不断移动
   index++;

  }

        // 返回整数作为最终结果。
  return negative ? - res : res;
 }
}

# 2、C++ 代码

class Solution {
public:
    int myAtoi(string s) {
        // 字符串的长度
        int n = s.length();

        // 设置有效数字的索引位置，初始化在第 0 个
        int index = 0;

        // 接收最终的结果
        int res = 0;

        // 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        // 所以在扫描的过程中，需要不断的判断最终的结果是正数还是负数
        // 根据字符的正和负来判断，最后一个字符决定
        // 默认为正数，即不是负数
        bool negative = false;


        // 根据第一点要求：读入字符串并丢弃无用的前导空格
        while( index < n && s[index] == ' ') {

            // 有效数字的索引位置不断移动
            index++;

        }

        // 根据第四点要求：如果字符串全是空格直接返回 0
        if( index == n) {
            
            // 直接返回 0
            return 0;

        }

        // 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        // 如果发现是负数，修改判断
        if( s[index] == '-' ) {

            // 认为是负数
            negative = true;

        }

        // 跳过正负号符号位
        if( s[index] == '-' || s[index] == '+' ) {

            // 有效数字的索引位置不断移动
            index++;

        }

        // 开始获取数字，一个数字一个数字去获取
        // 由于在字符串中可能存在数字之间夹杂的其它字符，所以出现这种情况需要截断
        while( index < n && s[index] >= '0' && s[index] <= '9' ) {

            // '0'的 ASCII 码是48，'1' 的是 49 
            // 获取数字，相当于字符串转整数操作
            int lastNum = s[index] - 48 ;

            // 根据第五点要求：需要判断数字是否合理
            // 先判断正数情况，大于 2147483647 的整数应该被固定为 2147483647 
            // 即如何发现之前积累的数字都大于了 214748364，比如最小为 214748365
            // 那么无论 lastNum 为多少，添加到尾部都会大于 214748364
            if( !negative && ( res > 214748364 || ( res == 214748364 && (lastNum == 8 || lastNum == 9 )))) {

                // 应该被固定为 2147483647 
                return 2147483647;

            }

            // 根据第五点要求：需要判断数字是否合理
            // 再判断负数情况，小于 -2147483648 的整数应该被固定为 -2147483648 
            if( negative && ( -res < -214748364 || ( -res == -214748364 && (lastNum == 8 || lastNum == 9 ) ))) {
                // 应该被固定为 -2147483648 
                return -2147483648;
            }

            // 否则说明可以添加上去
            res = res * 10 + lastNum;

            // 有效数字的索引位置不断移动
            index++;

        }

        // 返回整数作为最终结果。
        return negative ? - res : res;

    }
};

# 3、Python 代码

class Solution:
    def myAtoi(self, s: str) -> int:
        # 字符串的长度
        n = len(s)

        # 设置有效数字的索引位置，初始化在第 0 个
        index = 0

        # 接收最终的结果
        res = 0

        # 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        # 所以在扫描的过程中，需要不断的判断最终的结果是正数还是负数
        # 根据字符的正和负来判断，最后一个字符决定
        # 默认为正数，即不是负数
        negative = False

        # 根据第一点要求：读入字符串并丢弃无用的前导空格
        while index < n and s[index] == ' ' :

            # 有效数字的索引位置不断移动
            index += 1

        

        # 根据第四点要求：如果字符串全是空格直接返回 0
        if index == n :
            
            # 直接返回 0
            return 0

        # 根据第二点要求：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。
        # 如果发现是负数，修改判断
        if s[index] == '-' :

            # 认为是负数
            negative = True

        

        # 跳过正负号符号位
        if s[index] == '-' or s[index] == '+' :

            # 有效数字的索引位置不断移动
            index += 1

        

        # 开始获取数字，一个数字一个数字去获取
        # 由于在字符串中可能存在数字之间夹杂的其它字符，所以出现这种情况需要截断
        while index < n and s[index] >= '0'and s[index] <= '9' :

            # '0'的 ASCII 码是48，'1' 的是 49 
            # 获取数字，相当于字符串转整数操作
            lastNum =  ord(s[index]) - 48
            

            # 根据第五点要求：需要判断数字是否合理
            # 先判断正数情况，大于 2147483647 的整数应该被固定为 2147483647 
            # 即如何发现之前积累的数字都大于了 214748364，比如最小为 214748365
            # 那么无论 lastNum 为多少，添加到尾部都会大于 214748364
            if not negative and ( res > 214748364 or ( res == 214748364 and (lastNum == 8 or lastNum == 9 ))) :

                # 应该被固定为 2147483647 
                return 2147483647

        

            # 根据第五点要求：需要判断数字是否合理
            # 再判断负数情况，小于 -2147483648 的整数应该被固定为 -2147483648 
            if negative and ( -res < -214748364 or ( -res == -214748364 and (lastNum == 8 or lastNum == 9 ) )) :
                # 应该被固定为 -2147483648 
                return -2147483648
            

            # 否则说明可以添加上去
            res = res * 10 + lastNum

            # 有效数字的索引位置不断移动
            index += 1


        # 返回整数作为最终结果。
        return -res if negative else res

← LeetCode 7、整数反转 LeetCode 704、二分查找 →